package problems.daily;

/**
 * 793. 阶乘函数后K个零
 * <p>https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/
 *
 * @author habitplus
 * @since 2022/8/28 20:18
 */
public class DT793 {
    public int preimageSizeFZF(int k) {
        return (int) (help(k + 1) - help(k));
    }

    public long help(int k) {
        long r = 5L * k;
        long l = 0;
        long m;
        while (l <= r) {
            m = (l + r) / 2;
            if (zeta(m) < k) l = m + 1;
            else r = m - 1;
        }
        return r + 1;
    }

    public long zeta(long x) {
        long res = 0;
        while (x != 0) {
            res += x / 5;
            x /= 5;
        }
        return res;
    }
}






